package tree;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/23 17:24
 */
public class TreeOperation {
    public static int count;

    public static TreeNode createTree() {
        TreeNode a = new TreeNode('A'); // 'A' 是 char 类型，char -> int 类型，就是这个字符的 unicode 编码（ascii 是 unicode 编码的子集）
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        // 手动构建其关系
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        d.left = null;
        d.right = null;  // 这行可以省略
        e.left = null;
        e.right = h;
        f.left = null;
        f.right = null;
        g.left = null;
        g.right = null;
        h.left = null;
        h.right = null;

        // 返回根结点即可
        return a;
    }

    public static void main(String[] args) {
        TreeNode root = createTree();
        count = 0; //手动置为 0 ，避免数据已经修改过
        countNode(root);
        System.out.println(count);
        count = 0; //手动置为 0 ，避免数据已经修改过
        countNode(root);
        System.out.println(count);//不产生bug
        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
        System.out.println();
        System.out.println(getNodeSize(root));
        System.out.println(getLeafNodeSize(root));
        leafCount =0;
        preOrderCountLeaf(root);
        System.out.println(leafCount);
    }

    //由于静态属性修改过，初始不为 0 ，产生bug
    public static void main1(String[] args) {
        TreeNode root = createTree();
        preOrder(root);
        countNode(root);
        System.out.println(count);//8
        countNode(root);
        System.out.println(count);//16
        countNode(root);
        System.out.println(count);//24 bug
    }

    //参数：要遍历的树的根节点 root可能为null
    //经过时，打印
    //前序
    public static void preOrder(TreeNode root) {
        //root == null 不处理
        if (root == null) {
            return;
        }
        //tree 非空
        //处理根
        System.out.print(root);
        //采用相同方式，处理左子树
        preOrder(root.left);
        //采用相同方式，处理右子树
        preOrder(root.right);
    }
    //中序
    public static void inOrder(TreeNode root) {
        //root == null 不处理
        if (root == null) {
            return;
        }
        //tree 非空
        //采用相同方式，处理左子树
        inOrder(root.left);
        //处理根
        System.out.print(root);
        //采用相同方式，处理右子树
        inOrder(root.right);
    }
    //后序
    public static void postOrder(TreeNode root) {
        //root == null 不处理
        if (root == null) {
            return;
        }
        //tree 非空
        //采用相同方式，处理左子树
        postOrder(root.left);
        //采用相同方式，处理右子树
        postOrder(root.right);
        //处理根
        System.out.print(root);
    }
    public static void countNode(TreeNode root) {
        if (root == null) {
            return;
        }
        count++; //生命周期跨方法存在
        countNode(root.left);
        countNode(root.right);
    }
    //聚合的思想
    public static int getNodeSize(TreeNode root){
        if(root==null){
            return 0;
        }
        return getNodeSize(root.left)+getNodeSize(root.right)+1;
    }
    //求叶子节点的个数
    // 遍历的思想
    public static int leafCount;
    public static void preOrderCountLeaf(TreeNode root){
        if (root == null){
            return ;
        }

        //处理根
        //此时，我们不把root当根节点，当作一个普通节点
        //就检查这个节点是不是叶子节点
        if (root.left==null && root.right==null){
            leafCount++ ; //生命周期超越节点
        }
        preOrderCountLeaf(root.left);
        preOrderCountLeaf(root.right);
    }
    // 聚合的思想
    public static int getLeafNodeSize(TreeNode root){
        //1.空树
        if (root == null){
            return 0;
        }
        //2.只有一个节点的树
        if (root.left==null && root.right==null){
            return 1;
        }
        //3.剩余情况
        return getLeafNodeSize(root.left)+getLeafNodeSize(root.right);
    }
}
